googologywikiaorg-20200223-history
Talk:Fast-growing hierarchy
Excellent work on the comparisons to BEAF. I'm truly impressed. FB100Z • talk • 22:08, December 14, 2012 (UTC) What's this? http://cp4space.wordpress.com/2012/12/15/fast-growing-1/ --Cloudy176 (talk) 04:51, December 17, 2012 (UTC) Here are more comparisons between FGH and BEAF. http://googology.wikia.com/wiki/User_blog:Hyp_cos/BEAF_isn%27t_so_strong {hypcos} (talk) 01:35, October 2, 2013 (UTC) Hi Ikosarakt. You moved part of the list of functions to a subpage, which I reverted. There's nothing wrong with a long list. (Yes, there are a lot of equations, but maybe we could combine them with \eqnarray or something.) Also, subpages in the mainspace (like Fast-growing hierarchy/Beyond epsilon 0) are not actually supported by MediaWiki. FB100Z • talk • 22:25, December 18, 2012 (UTC) The main reason why I did this, that the content is loading too slow. I'm going to extend this list far beyond Feferman-Schutte ordinal, thus list can be even doubles in size. Ikosarakt1 (talk) 09:56, December 19, 2012 (UTC) :I could try converting this to \eqnarray with the help of the . That way we can load a whole lot of lines in just a few equations. FB100Z • talk • 20:41, December 23, 2012 (UTC) Good enough for government work. FB100Z • talk • 21:15, December 23, 2012 (UTC) What about creating separated articles about some ordinals? Ikosarakt1 (talk) 16:39, February 19, 2013 (UTC) :Example? FB100Z • talk • 23:25, February 20, 2013 (UTC) :Oh, I see. Such as an article about \(f_\omega(n)\), an article about \(f_{\varepsilon_0}(n)\), and an article about \(f_{\Gamma_0}(n)\)? Or do you mean articles about \(\omega\), \(\varepsilon_0\), and \(\Gamma_0\)? FB100Z • talk • 23:26, February 20, 2013 (UTC) About ordinals directly, and write how it compares (in different hierarchies) with googological notations. E.g. \(g_{Г_0}(n)\) (slow-growing hierarchy) is about {n,n,1,2}. Ikosarakt1 (talk) 09:48, February 21, 2013 (UTC) Lately (several days ago, actually) Chris Bird released this paper, in which he describes fast-growing hierarchy in terms of lower bounds in his array functions. This may be good comparison, because many of us know that Bowers' "array of" opperator is a bit ill-defined. By the way, why is there no article about Bird's notation on this wiki? LittlePeng9 (talk) 12:13, February 21, 2013 (UTC) Soon (within a few days), I shall write an article about it. Ikosarakt1 (talk ^ 11:15, March 9, 2013 (UTC) Church-Kleene so what exactly does \(f_{\omega^\text{CK}_1}(n)\) mean? I'm okay with keeping it here and pretending, but it's somewhat irritating. FB100Z • talk • 21:35, March 8, 2013 (UTC) Exactly? I don't know. Probably no one knows. Consider any sequence of length \(\omega\) converging to Church-Kleene ordinal, i.e. unbounded in \(\omega^\text{CK}_1\). For any ordinal notation infinitely many elements of these sequences are out-of-reach, so this sequence can't be recursively defined. So we can't even recursively define \(f_{\omega^\text{CK}_1}(n)\) as we would, say, \(f_{\epsilon_0}(n)\) (I don't even mention computing this function). All we can do is make a trivial choice of \(\omega^\text{CK}_1\)-recursive function (Sigma(n), for example) and call it \(f_{\omega^\text{CK}_1}(n)\).LittlePeng9 (talk) 21:50, March 8, 2013 (UTC) How far can we go? Although there _exist_ definitions of fundamental sequences for all the countable ordinals, i do not think it is possible to actually _define_ a set of fundamental sequences for all countable ordinals, simply because one cannot even refer to all countable ordinals; any ordinal notation must consist of finite strings over a finite alphabet, and therefore there can only be countably many ordinal notations. Deedlit11 (talk) 19:23, March 17, 2013 (UTC) :I have marked it as an "unresolved issue" for the moment. It'd be super-awesome if someone could write up a section on how and why things get messy starting with Church-Kleene. FB100Z • talk • 19:33, March 17, 2013 (UTC) :To define fundamental sequences for any ordinal we need to define every ''smaller ordinal. To do this, we need ordinal notation. But every ordinal notation has limit smaller than \(\omega^{CK}_1\). It's said in definition of Church-Kleene ordinal after all - it is supermum of all ordinals with notations (if it had notation itself, its succesor would have one too. But supermum can't be smaller than any element - contradiction). LittlePeng9 (talk) 19:46, March 17, 2013 (UTC) :Actually you can define fundamental sequences up to the Church-Kleene ordinal and beyond. I'll explain how to do this in my next blog post. Deedlit11 (talk) 20:11, March 17, 2013 (UTC) Faster-growing hierarchies? So is there any way to modify these rules to produce an even more powerful hierarchy with an equally elegant definition? What about this, for example? \+ 1}(n) = f_\alpha^{f_\alpha^{f_\alpha^{.^{.^..}.}(n)}(n)}(n)\ FB100Z • talk • 20:23, March 17, 2013 (UTC) Yes, you could do that. Note that, in the old version of the fast-growing hierarchy, \\approx f_{\alpha+2} (n) \. So taking one step in the new hierarchy is equivalent to taking two steps in the traditional hierarchy. If we call the old hierarchy F and the new hierarchy f, we get \\approx f_{\omega*\alpha}(n)\. So we don't really get any further. Even if we could somehow define a step that was as strong as taking \(\omega\) steps in the regular fast-growing hierarchy, the regular hierarchy would still catch up at the ordinal \(\omega^{\omega}\). The power of the notation comes from recursion and the strength of ordinal notation systems. Deedlit11 (talk) 20:43, March 17, 2013 (UTC) :I just noticed that before you posted. Is there anything we can do to make a simple system non-negligibly stronger than FGH? FB100Z • talk • 21:08, March 17, 2013 (UTC) Well, one possibility is to redefine fundamental sequences. In "An extremely sharp phase transition threshold for the slow growing hierarchy" there is explained how choice of these sequences may affect hierarchy. Maybe we can have similar results for FGH? LittlePeng9 (talk) 21:15, March 17, 2013 (UTC) :@FB100Z: I can't think of anything. I don't think there is anything simple that is significantly stronger than the iteration of the fast-growing hierarchy, or we would have heard about it. So anything signficantly stronger than the fast-growing hierarchy will take some work. But then there will always be some closure ordinal where the fast-growing hierarchy catches up to the new hierarchy, so it's not clear that the extra work is worth it. :Actually, I would say that the Hardy hierarchy is higher on the simplicity/growth rate scale than the fast-growing hierarchy, since the definition is simpler (adding one is simple than taking the nth iterate), and yet the Hardy hierarchy catches up with the fast-growing hierachy at all major ordinals! :@LittlePeng9: The fast-growing hierarchy may be susceptible to changes in the definition of fundamental sequences; but I feel that, while we may make the growth rate of the fast-growing hierarchy slower by changing the fundamental sequences, I don't think one can make it faster with any natural definition. The reason is, there is a natural limit to the growth rate: for a natural, sufficiently strong theory with proof theoretic ordinal alpha, for any ordinal beta less than alpha we will have F_beta(n) a provably recursive function of the theory, as the theory can handle recursion up to any ordinal less than alpha. So to grow faster than the provably recursive functions of the theory, we will have to do it "all in one blow" so to speak, rather than let the recursion handle it; that is, we will have to define a very fast growing fundamental sequence. I don't think such a fundamental sequence can be described as natural. Deedlit11 (talk) 23:13, March 17, 2013 (UTC) :@Googleaarex: I know! f_(alpha)(n) = f_(omega^f_(omega^f_(omega^...f_(omega^n)(n))(n))(n))(n) (n times)) Aarex (talk) 01:20, March 18, 2013 (UTC) :Eh? That gives you the same function for all alpha. Deedlit11 (talk) 01:50, March 18, 2013 (UTC) :I toyed briefly with feeding FGH back into itself, e.g. \(f_{f_\omega(\omega)}(n)\). The obvious problem is that \(f_\alpha(\omega) = f_{\alpha\omega}(\omega) = f_\alpha(\omega)\). FB100Z • talk • 00:03, March 21, 2013 (UTC) ::What you can do is define \(f_{\alpha}(\beta) = \bigcup_{\gamma < \alpha} f_{\gamma}(\beta)\) when \(\alpha\) is a limit ordinal. That gives you an interesting hierarchy. Deedlit11 (talk) 01:32, March 22, 2013 (UTC) :::Hrm. So \(f_0(\omega) = \omega + 1\) and \(f_1(\omega) = \omega \times 2\). What's \(f_2(\omega)\)? FB100Z • talk • 01:39, March 22, 2013 (UTC) ::::\(f_2(\omega) = \omega \times 2^{\omega} = \omega \times \omega = \omega^2\). Deedlit11 (talk) 02:29, March 22, 2013 (UTC) :::::oh, ok. \(f_3(\omega) = \omega^{2\omega} = \omega^\omega\), \(f_4(\omega) = \sup\{\omega, \omega^\omega, \omega^{\omega \times \omega^\omega} = \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}}, \ldots\} = \varepsilon_0\), which looks quite promising. Since we're going through different recursion levels, I'll take a wild stab and guess that churchy is the first fixed point of \(\alpha \mapsto f_\alpha(\omega)\). FB100Z • talk • 03:19, March 22, 2013 (UTC) ::::::Churchy? What's that? Deedlit11 (talk) 03:29, March 22, 2013 (UTC) :::::::\(\omega_1^\text{CK}\), the Church-Kleene ordinal. I have this weird habit of making dumb nicknames for things. :::::::On second thought, just having omega as the argument is wimpy. Maybe it'd be "better" to have supremum of all ordinals constructible using 0, 1, omega, and the map \(\alpha, \beta \mapsto f_\alpha(\beta)\). FB100Z • talk • 03:42, March 22, 2013 (UTC) ::::::::Ah, the Church-Kleene ordinal. No, the first fixed point of \(\alpha \mapsto f_\alpha(\omega)\) is not \(\omega_1^\text{CK}\); in fact \(\omega_1^\text{CK}\) is completely unreachable of any recursive notation. The closure ordinal of \(\alpha \mapsto f_\alpha(\omega)\) is the same as the closure ordinal of \(\alpha, \beta \mapsto f_\alpha(\beta)\), namely \(\Gamma_0\). Deedlit11 (talk) 04:00, March 22, 2013 (UTC) :::::::::Aw, shucky darn. So \(\alpha, \beta \mapsto f_\alpha(\beta)\) is no more powerful than the Veblen hierarchy. FB100Z • talk • 05:52, March 22, 2013 (UTC) ::::::::::Yeah, it is hard to beat the traditional notations. Deedlit11 (talk) 06:16, March 22, 2013 (UTC) :::::::::::: So does this means feeding FGH back into itself is no way bigger than the orginal FGH with Gamma 0? Quite sad. —Preceding unsigned comment added by D57799 (talk • ) Going backwards Here's an odd extension. \- 1}(n) = \min\{m|f_\alpha^m(m) \geq n\}\ I may have the formula wrong, but it's pretty clear what it's supposed to mean. If \(\alpha\) is a successor ordinal, \(\alpha - 1\) is well-defined and the definition is consistent. If \(\alpha\) is a limit ordinal, \(\alpha - 1\) is just a symbol but \(f_{\alpha - 1}(n)\) is still a valid function. FB100Z • talk • 05:20, April 8, 2013 (UTC) :Yeah, the formula is wrong - it defines the inverse function of \(f_{\alpha+1} (n)\), which isn't \(f_{\alpha-1}(n)\). I don't know how to easily define \(f_{\alpha-1}(n)\) from \(f_{\alpha}(n)\), we want some function \(g\) such that \(g^n(n) = f_{\alpha}(n)\), but there's a lot of potential functions which could do that. Deedlit11 (talk) 05:34, April 8, 2013 (UTC) ::Hrm, maybe it'd be easier to define inverse variations on SGH and the Hardy hierarchy. FB100Z • talk • 05:35, April 8, 2013 (UTC) :::Hmm, for the Hardy hierarchy you can define \(H_{\alpha-1}(n) = H_{\alpha}(n-1)\), but the problem comes in defining \(H_{\alpha-1}(0)\), which you can't generate easily from \(H_{\alpha}(n)\). For the slow-growing hierarchy, \(G_{\alpha-1}(n) = G_{\alpha}(n) - 1\) will work fine, if you allow negative numbers. Deedlit11 (talk) 05:45, April 8, 2013 (UTC) What's "growth rate"? ----- Imagine this: a function p(n). And for any n, \(f_\omega(n)Tiao 18:32, November 23, 2013 (UTC) ::I reverted Aarex's edits because he removed too many comparisons (those after \(\varepsilon_\omega\)) and changed the comparisons before that. Since the newly added comparisons were incorrect (the edit included comparisons such as \(f_{\varepsilon_0}(n) > \lbrace n,n \uparrow\uparrow n-1 (1) 2 \rbrace\), while \(f_{\varepsilon_0}(n) > X \uparrow\uparrow n-1 \&\ n \) is correct, and much larger), I reverted the edits. -- ☁ I want more ⛅ 06:59, November 24, 2013 (UTC) Continued FGH Where I can read about FGH after f_{\varepsilon_{\vartheta(\Omega_\omega)+1}}(n) ? Continued FGH on our website can be found only in the user's blogs! eg what \(\psi(\Psi_{\Xi(\alpha \mapsto K_\alpha,0)}(0))\)? May need to expand this article? Konkhra (talk) 04:08, April 22, 2014 (UTC) :Here, but prepare to complicated and non-newcomer-friendly math. Ikosarakt1 (talk ^ ) 18:35, May 3, 2014 (UTC) What happened? FGH just appear up to e(0). What happened? -- A Large Number Googologist -- 02:57, October 4, 2014 (UTC) BEAF beyond e(0) level is not well-defined, so the comparisons were deleted. {hyp/^,cos} (talk) 04:39, October 4, 2014 (UTC) Idea How about using this page for explaining the fundamental sequences, and making subpages for the comparisons with BEAF, ExE, HAN, BAN, etc? Wythagoras (talk) 06:45, October 4, 2014 (UTC) I like the idea of adding BAN (Bird's Array Notation) Michael Tiemann (talk) 02:51, October 23, 2015 (UTC) OBJECTION! If everything beyond X^^X & n is not well-defined, why are comparisons in the SGH page? -- A Large Number Googologist -- 19:55, October 11, 2014 (UTC) : Why the hell are you complaining about it here? LittlePeng9 (talk) 19:57, October 11, 2014 (UTC) : Yes it IS well-defined: ω↑↑↑ω=2φ0, ω{ω}ω=ωφ0, etc., and{ω,ω,1,2}=1φ0φ0φ0. 15:42, December 31, 2017 (UTC) ::: (1) Whatever definition you have in mind for ordinal hyperoperators, it has absolutely nothing to do with the question of whether BEAF is well-defined beyond tetrational arrays. Unless you can show (for example) how the tritri elements of 3↑↑↑3 & 3 are arranged and how such an array should be evaluated, you haven't made any progress towards defining BEAF beyond epsilon-0. ::: (2) Even if you found a way to extend BEAF, it would be ''your extension. It will not change the fact that BEAF, as Bowers defined it, breaks down beyond tetrational arrays. ::: (3) You've given no justification what-so-ever for the claim that your system of ordinal hyperoperators is well-defined. Hint: posting baseless claims on dozens of pages does not constitute a "justification". PsiCubed2 (talk) 15:54, December 31, 2017 (UTC) See http://googology.wikia.com/wiki/Talk:Slow-growing_hierarchy -- A Large Number Googologist -- 20:33, October 11, 2014 (UTC) : Repeating my question: Why the hell are you complaining about it here? LittlePeng9 (talk) 20:36, October 11, 2014 (UTC) Ok, you can delete this topic -- A Large Number Googologist -- 01:04, October 12, 2014 (UTC) Question Who made FGH? -- A Large Number Googologist -- 00:12, October 19, 2014 (UTC) As I know, this version of FGH was proposed by Martin Löb and Stan S. Wainer in 1970 as extension of Grzegorczyk hierarchy to transfinite ordinals and that is why it is known as Wainer hierarchy--Denis Maksudov (talk) 22:31, November 4, 2016 (UTC) past epsilon-zero i really think we should put some mention of ordinals past epsilon-zero on the fgh page, but i'm not sure how Cookiefonster (talk) 19:54, October 28, 2014 (UTC) What about using Bird's Array Notation in addition or in preference to BEAF? They are very similar up to \(\varepsilon_0\). But Bird's notation (as extended) gets us to \(\theta(\Omega_\Omega)\). It would avoid the nasty "structures" problem. Michael Tiemann (talk) 17:22, October 22, 2015 (UTC) :I (and a few others) have doubts on the validity of Bird's comparisons. His supporting arguments are minimal and his approximations are educated guesses at best. -- ve 05:33, October 23, 2015 (UTC) Is it possible to create a function that diagonalizes over the fast-growing hierarchy? Or can it not be done since you would need to individually define the fundamental sequence for each ordinal? : Even assuming we have figured out a fundamental sequence for every countable ordinal, we can't ever make sense of \(f_{\omega_1}\) (and this is what "diagonalization over the FGH" would be), since for that we'd need a fundamental sequence for \(\omega_1\), which doesn't exist. LittlePeng9 (talk) 10:28, November 1, 2016 (UTC) What does > replace almost all of the = for the equations? Do we not have an exact formula for each function? Nathan da' R. 22:13, March 2, 2017 (UTC) No we don't. .Chronolegends (talk) 22:43, March 2, 2017 (UTC) :It is impossible to calculate \(\omega^{CK}_1\) (which can't make ordinals with other ordinals less than \(\omega^{CK}_1\) using the ordinal notations.), so you can't make diagonalizes FGH. Googleaarex (talk) ::We can extend FGH up to any countable ordinal, including ones beyond \(\omega_1^\text{CK}\). We don't need a recursive ordinal notation of any sort, just a system of fundamental sequences. \(\omega_1\) is where the problems arise. LittlePeng9 (talk) 06:09, March 3, 2017 (UTC) 21:54, January 10, 2018 (UTC) Here is the slowest function with an uncountable growth rate: \(f_{\omega_{1}}(n)\) :\(f_{\omega_1}(n)\) is ill-defined. There is no fundamental sequence for \(\omega_1\). Rpakr (talk) 09:47, January 11, 2018 (UTC) A bit of a stupid question Does anyone know of a low-level fgh calculator? E.g. something that gives you fgh_(small value)(n)? Moooosey (talk) 21:26, October 3, 2019 (UTC) : Since fgh_2 is already greater than the exponential, I guess that "the small value" is supposed to be bounded by 3 as long as n is greater than 2. If so, you can just directly compute it using the formula f_0(n) = n+1, f_1(n) = 2n, and f_2(n) = 2^n×n. : p-adic 22:04, October 3, 2019 (UTC) Minus Ordinal FGH Hey, everyone, have you thought that how much is \( f_{-1}(10) \),\( f_{-1}(100) \), and \( f_{-1}(n) \)? : FGH is a hierarchy of ordinal-indexed functions, but -1 is not an ordinal, it’s just an integer number. The least ordinal is zero.--Denis Maksudov (talk) 20:37, February 14, 2020 (UTC)